#pragma once

#include "TypeDefin.h"

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;
/*
 *230. 二叉搜索树中第K小的元素
中等
689
相关企业
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。


示例 1：


输入：root = [3,1,4,null,2], k = 1
输出：1
示例 2：


输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
 * */



int ret = 0;
int s = 0;

void kthSmallest_r(TreeNode *root, int k) {
    //中序遍历
    if (!root)
        return;

    kthSmallest_r(root->left, k);

    s++;
    if (s == k) {
        ret = root->val;
        return;
    }

    kthSmallest_r(root->right, k);

}

int kthSmallest(TreeNode *root, int k) {
    kthSmallest_r(root, k);
    return ret;

}

//非递归方式
//中序遍历 左跟右
int kthSmallest1(TreeNode *root, int k) {

    stack<TreeNode *> s;
    s.push(root);
    auto cur = root;
    int count = 0;
    while (!s.empty() || cur) {
        while (cur->left) {
            cur = cur->left;
            s.push(cur);
        }
        auto cur = s.top();
        s.pop();
        count++;
        if (count == k)
            return cur->val;

        if (cur->right)
            cur = cur->right;

    }

    return -1;

}
